Regulated rewriting

Regulated rewriting is a specific area of formal languages studying grammatical systems which are able to take some kind of control over the production applied in a derivation step. For this reason, the grammatical systems studied in Regulated Rewriting theory are also called "Grammars with Controlled Derivations". Among such grammars can be noticed:

Contents

Matrix Grammars

Basic concepts

Definition
A Matrix Grammar, MG, is a four-tuple G = (N, T, M, S) where
1.- N is an alphabet of non-terminal symbols
2.- T is an alphabet of terminal symbols disjoint with N
3.- M = {m_1, m_2,..., m_n} is a finite set of matrices, which are non-empty sequences m_{i} = [p_{i},...,p_{i_{k(i)}}], with k(i)\geq 1, and 1 \leq i \leq n, where each p_{i_{j}} 1\leq j\leq k(i), is an ordered pair p_{i_{j}} = (L, R) being L \in (N \cup T)^*N(N\cup T)^*, R \in (N\cup T)^* these pairs are called "productions", and are denoted L\rightarrow R. In these conditions the matrices can be written down as m_i = [L_{i_{1}}\rightarrow R_{i_{1}},...,L_{i_{k(i)}}\rightarrow R_{i_{k(i)}}]
4.- S is the start symbol

Definition
Let MG = (N, T, M, S) be a matrix grammar and let P the collection of all productions on matrices of MG. We said that MG is of type i according to Chomsky's hierarchy with i=0,1,2,3, or "increasing length" or "linear" or "without \lambda-productions" if and only if the grammar G=(N, T, P, S) has the corresponding property.

The classic example (taken from [5] with change of nonterminals names)

The context-sensitive language L(G) = \{ a^nb^nc^n�: n\geq 1\} is generated by the CFMG G =(N, T, M, S) where N = \{S, A, B, C\} is the non-terminal set, T = \{a, b, c\} is the terminal set, and the set of matrices is defined as M�: \left[S\rightarrow abc\right], \left[S\rightarrow aAbBcC\right], \left[A\rightarrow aA,B\rightarrow bB,C\rightarrow cC\right], \left[A\rightarrow a,B\rightarrow b,C\rightarrow c\right].

Time Variant Grammars

Basic concepts
Definition
A Time Variant Grammar is a pair (G, v) where G = (N, T, P, S) is a grammar and v: \mathbb{N}\rightarrow 2^{P} is a function from the set of natural numbers to the class of subsets of the set the productions.

Programmed Grammars

Basic concepts

Definition

A Programmed Grammar is a pair (G, s) where G = (N, T, P, S) is a grammar and s, f: P\rightarrow 2^{P} are the success and fail functions from the set of productions to the class of subsets of the set the productions.

Grammars with regular control language

Basic concepts

Definition
A Grammar With Regular Control Language, GWRCL, is a pair (G, e) where G = (N, T, P, S) is a grammar and e is a regular expression over the alphabet of the set the productions.

A naive example

Consider the CFG G = (N, T, P, S) where N = \{S, A, B, C\} is the non-terminal set, T = \{a, b, c\} is the terminal set, and the productions set is defined as P = \{p_0, p_1, p_2, p_3, p_4, p_5, p_6\} being p_0 = S\rightarrow ABC p_1 = A\rightarrow aA, p_2 = B\rightarrow bB, p_3 = C\rightarrow cC p_4 = A\rightarrow a, p_5 = B\rightarrow b, and p_6 = C\rightarrow c. Clearly, L(G) = \{ a^*b^*c^*\}. Now, considering the productions set P as an alphabet (since it is a finite set), define the regular expression over P: e=p_0(p_1p_2p_3)^*(p_4p_5p_6).

Combining the CFG grammar G and the regular expression e, we obtain the CFGWRCL (G,e) =(G,p_0(p_1p_2p_3)^*(p_4p_5p_6)) which generates the language L(G) = \{ a^nb^nc^n�: n\geq 1\}.

Besides there are other grammars with regulated rewriting, the four cited above are good examples of how to extend context-free grammars with some kind of control mechanism to obtain a Turing machine powerful grammatical device.

Sources

[1] Salomaa, Arto Formal languages Academic Press, 1973 ACM monograph series

[2] G. Rozenberg, A. Salomaa, (eds.) Handbook of formal languages Berlin; New York : Springer, 1997 ISBN 3540614869 (set) (3540604200 : v. 1; 3540606483 : v. 2; 3540606491: v. 3)

[3] Regulated Rewriting in Formal Language Theory Jurgen Dassow; G. Paun Pages: 308. Medium: Hardcover. Year of Publication: 1990 ISBN:0387514147. Springer-Verlag New York, Inc. Secaucus, NJ, USA

[4] Grammars with Regulated Rewriting Jurgen Dassow Otto-von-Guericke Available at: [1] and [2] ([3])

[5] Some questions of language theory S. Abraham in Proceedings of the 1965 International Conference On Computational Linguistics pp 1 - 11, Bonn, Germany Year of Publication: 1965 Available at: [4]